package 迪杰斯特拉Dijkstra算法;

import java.util.Arrays;

public class 迪杰斯特拉算法 {
	public static void main(String[] args) {
		//https://www.cnblogs.com/skywang12345/p/3711516.html
		//https://blog.csdn.net/qq_34842671/article/details/90083037
		int[][] matrix = new int[7][7];
		int N = 65535;
//		matrix[0]=new int[] {N,5,7,N,N,N,2};
//		matrix[1]=new int[]{5,N,N,9,N,N,3};
//		matrix[2]=new int[] {7,N,N,N,8,N,N}; 
//		matrix[3]=new int[] {N,9,N,N,N,4,N}; 
//		matrix[4]=new int[]{N,N,8,N,N,5,4};
//		matrix[5]=new int[] {N,N,N,4,5,N,6};
//		matrix[6]=new int[] {2,3,N,N,4,6,N};
		
		matrix[0]=new int[] {0,5,7,N,N,N,2};
		matrix[1]=new int[]{5,0,N,9,N,N,3};
		matrix[2]=new int[] {7,N,0,N,8,N,N}; 
		matrix[3]=new int[] {N,9,N,0,N,4,N}; 
		matrix[4]=new int[]{N,N,8,N,0,5,4};
		matrix[5]=new int[] {N,N,N,4,5,0,6};
		matrix[6]=new int[] {2,3,N,N,4,6,0};
//		dijstra(matrix, 2);
		dijstra1(matrix, 2);
	}
	
	/**
	 * 迪杰斯特拉
	 * @param matrix 邻接矩阵
	 * @param source 起始位置
	 */
	public static void dijstra(int[][] matrix, int source) {
		//是否访问
		int[] visited = new int[matrix.length];
		//顶点之间距离
		int[] dis = new int[matrix.length];
		//顶点前驱
		int[] prev = new int[matrix.length];
		//极大值
		int N = 65535;
		
		
		//初始化
		for (int i = 0; i < matrix.length; i++) {
			//无访问
			visited[i] = 0;
			//距离极大
//			dis[i] = N;
			//两种不同的写法，一种是初始全0，另一种初始会有起始顶点的连接关系
			dis[i] = matrix[source][i];
			//无前驱
			prev[i] = 0;
		}
		
		//对于起始顶点初始化
		//已访问
		visited[source] = 1;
		//前驱是自己
		prev[source] = 0;
		dis[source] = 0;
		
		System.out.println(Arrays.toString(visited));
		System.out.println(Arrays.toString(prev));
		System.out.println(Arrays.toString(dis));
		System.out.println("-----------------");
		//开始遍历，每次找出一个顶点的最小路径，因为最后一个顶点不用访问，因为没路了
		//此处 i 只用来计数
		for(int i = 1; i < matrix.length; i++) {
			
			//首先寻找临近顶点最小路径，即在未访问顶点查找离起始顶点source路径最小的
			//虽然全部遍历了一遍(理论上只有相邻的顶点才能遍历)，但是不影响，
			//因为只有最近的顶点才是路径最小的，不会找错
			//首先定义一个极大值，用来找最小值
			int min = 6553;
			//定义一个k，保存最小值下标
			int k = -1;
			
			//开始查找
			for(int j = 0; j < matrix.length; j++) {
				if(visited[j] == 0 &&  dis[j]  < min) {
					min = dis[j];
					k = j;
				}
			}
			//标记最小值k已被访问
			visited[k] = 1;
			
			//dis[k] = min;
			//松弛：在原本是一段直线的路径上（A-C）添加其他结点达到多段路径（A-B-C），松弛之后可能比原始
			//路径更短
			//此步也叫更新最短路径和前驱结点，在找到最小顶点后，从原始顶点出发到最小顶点，重新更新剩下的
			for(int j = 0; j < matrix.length; j++) {
				if(visited[j] == 0 && dis[k] + matrix[k][j] < dis[j]) {
					dis[j] = dis[k] + matrix[k][j];
					prev[j] = k;
				}
			}
//			System.out.println(Arrays.toString(dis)+"``");
			
		}	
		//[7, 12, 0, 17, 8, 13, 9]
		
		System.out.println(Arrays.toString(dis));
		System.out.println(Arrays.toString(prev));
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(matrix[i][j]+"\t");
			}
			System.out.println();
		}
	}
	
	
	
	
	/**
	 * 迪杰斯特拉
	 * @param matrix 邻接矩阵
	 * @param source 起始位置
	 */
	public static void dijstra1(int[][] matrix, int source) {
		//是否访问
		int[] visited = new int[matrix.length];
		//顶点之间距离
		int[] dis = new int[matrix.length];
		//顶点前驱
		int[] prev = new int[matrix.length];
		//极大值
		int N = 65535;
		
		
		//初始化
		for (int i = 0; i < matrix.length; i++) {
			//无访问
			visited[i] = 0;
			//距离极大
			dis[i] = N;
//			dis[i] = matrix[source][i];
			//无前驱
			prev[i] = 0;
		}
		
		//对于起始顶点初始化
		//已访问
		//visited[source] = 1; !!!!!!!!如果dis={0}就不要在这里访问，因为visited[0]=1 && dis[0]<min
		//前驱是自己
		prev[source] = 0;
		dis[source] = 0;
		
		System.out.println(Arrays.toString(visited));
		System.out.println(Arrays.toString(prev));
		System.out.println(Arrays.toString(dis));
		System.out.println("-----------------");
		//开始遍历，每次找出一个顶点的最小路径，因为最后一个顶点不用访问，因为没路了
		//此处 i 只用来计数
		for(int i = 1; i < matrix.length; i++) {
			
			//首先寻找临近顶点最小路径，即在未访问顶点查找离起始顶点source路径最小的
			//虽然全部遍历了一遍(理论上只有相邻的顶点才能遍历)，但是不影响，
			//因为只有最近的顶点才是路径最小的，不会找错
			//首先定义一个极大值，用来找最小值
			int min = 6553;
			//定义一个k，保存最小值下标
			int k = -1;
			
			//开始查找
			for(int j = 0; j < matrix.length; j++) {
				if(visited[j] == 0 &&  dis[j]  < min) {
					min = dis[j];
					k = j;
				}
			}
			//标记最小值k已被访问
			visited[k] = 1;
			
			//dis[k] = min;
			//松弛：在原本是一段直线的路径上（A-C）添加其他结点达到多段路径（A-B-C），松弛之后可能比原始
			//路径更短
			//此步也叫更新最短路径和前驱结点，在找到最小顶点后，从原始顶点出发到最小顶点，重新更新剩下的
			for(int j = 0; j < matrix.length; j++) {
				if(visited[j] == 0 && dis[k] + matrix[k][j] < dis[j]) {
					dis[j] = dis[k] + matrix[k][j];
					prev[j] = k;
				}
			}
			//理解为原始路径是一个点到另一个点，在找到最短路径之后就是一条路到一个点，
			//判断是否有直达的路径是否更短，或者链接的路径比直达的更短
			
		}	
		//[7, 12, 0, 17, 8, 13, 9]
		
		System.out.println(Arrays.toString(dis));
		System.out.println(Arrays.toString(prev));
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(matrix[i][j]+"\t");
			}
			System.out.println();
		}
	}
	

}
